package com.love.labuladong;

/**
 * @Author : zh
 * @Description : 二分查找 ：适用于排序数组
 * @Date : 2024-05-13 16:13
 */
public class BanarySearch {


    public static void main(String[] args) {
        int[] nums = {1,2,2,3,4,5,8,9};

        int i = left_bound(nums, 9);
        System.out.println(i);

        int l = left_bound2(nums, 9);
        System.out.println(l);


        int j = right_bound(nums, 2);
        System.out.println(j);


    }


    /**
     * 查左边界
     * @param nums
     * @param target
     * @return
     */
    static int  left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 搜索区间为 [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 搜索区间变为 [mid+1, right]
                // 在多个相同数字的情况下，找左边边界命中的数字，依然适用二分法
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }


    /**
     * 数组中有重复数字，返回命中数最左边的数字的下标
     * @param nums
     * @param target
     * @return
     */
    static int left_bound2(int[] nums,int target){
        int left = 0,right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >>> 1);
            if(nums[mid] == target){
                // 因为 while 的 条件范围 [left,right),也就是在这个循环里 left 是达不到 right 的
                // left == right 时，已经跳出循环，此时，相当于 num[left] = num[right]
                right = mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }
        }
        if(left == nums.length || nums[left] != target){
            return -1;
        }
        return left;
    }




    /**
     * 数组中有重复数字，返回命中数最右边的数字的下标
     * @param nums
     * @param target
     * @return
     */
    static int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
        }
        // 这里改为检查 right 越界的情况，见下图
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }

}
